package skiplist

import "math/rand/v2"

// 节点按顺序排，
// 每个节点都有 nexts 数组，它就像一根竖起来的杆子，每个杆子上有 0 到 31 层，
// 对于杆子上每一层来说，它保存的是在它那一层的下一跳节点，它只能比当前节点大，或者为 nil（可以看作无穷大），
// 插入节点的时候，先检查是否已存在，已存在只把节点的 cnt+1，
// 不存在的话，计算一个随机的新竿子高度 n，新竿子上从 0 到 n-1 每一层都要找到合适的下一跳节点，

type Skiplist struct {
	head *node
}

type node struct {
	val   int
	nexts []*node // 保存各个 level 下一跳的节点
	cnt   int
}

func Constructor() Skiplist {
	return Skiplist{
		head: &node{
			nexts: make([]*node, 0, 32),
		},
	}
}

func (s *Skiplist) Search(target int) bool {
	return nil != s.search(target)
}

func (s *Skiplist) search(target int) *node {
	// nexts 就是节点上竖起的竿子，
	// nexts[level] 就是竿子上保存的下一跳节点，它只能是右边的某个值比它大的节点或者 nil，
	nexts := s.head.nexts
	// 想像遍历一个三角形的台阶，只能向右和向下，每个台阶都是一个 node
	for level := len(nexts) - 1; level >= 0; level-- { // 在同一个竿子上换层
		for nexts[level] != nil && nexts[level].val < target { // 在同一层中换竿子
			// 切换到下一跳节点的竿子上
			nexts = nexts[level].nexts
		}
		if nexts[level] != nil && nexts[level].val == target { // 找到了
			return nexts[level]
		}
	}
	return nil
}

// 计算最大层数
func (s *Skiplist) roll() int {
	level := 1
	for rand.Float32() > 0.5 && level < 32 {
		level++
	}
	return level
}

func (s *Skiplist) Add(num int) {
	// 查找是否已存在
	if node := s.search(num); node != nil {
		node.cnt++
		return
	}

	// 计算一个随机数作为新节点的层级数
	levelNew := s.roll()
	// 补齐头指针的层级
	for i := len(s.head.nexts); i < levelNew; i++ {
		s.head.nexts = append(s.head.nexts, nil)
	}

	// 构造新节点
	newNode := &node{
		val:   num,
		nexts: make([]*node, levelNew),
		cnt:   1,
	}

	// nexts 就是节点上竖起的竿子，
	// nexts[level] 就是竿子上保存的下一跳节点，它只能是右边的某个值比它大的节点或者 nil，
	nexts := s.head.nexts
	// 插入新节点的竿子，
	// 在新节点的竿子上，找到每一层应该放入的下一跳节点，
	for level := levelNew - 1; level >= 0; level-- { // 从上到下遍历
		for nexts[level] != nil && nexts[level].val < num { // 在不同竿子的同一层节点之间跳跃
			// 新节点比当前节点竿子上的下一跳节点的值还大，不符合要求，
			// 要切换到下一跳节点的竿子上，继续下一轮判断，
			nexts = nexts[level].nexts
		}

		// 新节点比当前节点竿子上的下一跳节点的值小（等于情况上面已经处理了），或者下一跳节点是 nil，
		// 新节点就能插入到当前节点和下一跳节点之间，所以下一跳节点可以放到新节点的竿子上，
		// 下面的操作就像在链表的两个节点之间插入一个新节点：
		// 假设要在 A->B 之间插入 C，
		// 先 c->B，再 A->C
		newNode.nexts[level] = nexts[level]
		nexts[level] = newNode

		// 注意，进入下一轮循环时，是沿着现有的竿子往下一层，不需要重新回到头结点的竿子上，
		// 因为当前竿子会一直延伸到第 0 层，从当前层到第 0 层，左边的任意竿子上的下一跳节点值最多只能是当前节点打住，
		// 也就是当前竿子所在节点的值比左边所有竿子所在节点值都大，目标又比当前竿子所在节点值大，所以只需要往右边的竿子继续找
	}
}

func (s *Skiplist) Erase(num int) bool {
	// 先查找节点是否存在
	node := s.search(num)
	if node == nil {
		return false
	} else if node.cnt > 1 {
		node.cnt--
		return true
	}

	nexts := s.head.nexts
	// 删除节点
	// 遍历每一层，把目标节点上竖起的竿子整个删掉，也就是把竿子上的节点都挪走
	for level := len(node.nexts) - 1; level >= 0; level-- {
		// 遍历每一层的链表
		for nexts[level] != nil && nexts[level].val < num {
			nexts = nexts[level].nexts
		}

		// 删除找到的链表节点
		if nexts[level] != nil && nexts[level].val == num {
			nexts[level] = nexts[level].nexts[level]
			continue
		}
	}

	// 还要删除头指针中清空的level
	level := len(s.head.nexts) - 1
	for ; level >= 0; level-- {
		if s.head.nexts[level] != nil {
			break
		}
	}
	s.head.nexts = s.head.nexts[:level+1]
	return true
}
